#include <iostream>
#include <vector>

using namespace std;
// 684. 冗余连接
// 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。
// 添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。
// 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        n = 0;
        for(vector<int>& edge : edges) {
            int x = edge[0];
            int y = edge[1];
            n = max(n, max(x, y));  // 在输入里出现的最大的点数即为n
        }
        to = vector<vector<int>> (n+1, vector<int>()); // 1...n
        visited = vector<bool>(n+1, false);
        // to初始化，加边
        for(vector<int>& edge : edges) {
            int x = edge[0];
            int y = edge[1];
            // 出边数组加边的方法
            to[x].push_back(y);
            to[y].push_back(x);
            // 每加一条边，就判断一遍
            hasCycle = false;
            for(int i = 1; i <= n; i++)
                visited[i] = false;
            dfs(x,0);   // 不要从根节点1出发，father是0，表示不存在。从刚加的这条边出发
            if(hasCycle) {
                return edge;
            }
        }
        return {};
    }

private:
    // 图的深度优先遍历，判断环的模板
    // 从x出发，找到所有的点
    void dfs(int x, int father) {
        visited[x] = true;
        // 出边数组访问x能到的周边点的方法
        for(int y : to[x]) {
            if (y == father) continue;
            if(!visited[y]) dfs(y, x);
            else hasCycle = true;
        }
//        visited[x] = false;
    }
    vector<vector<int>> to; // 出边数组
    int n;  // 点的个数
    vector<bool> visited;
    bool hasCycle;
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
